leetcode Count Prim

Posted on   |   In   |  

利用埃氏筛选法筛选素数

Count Prime

link
Description:

Count the number of prime numbers less than a non-negative number, n.
求出n以内的所有素数。
这道题目如果用循环来逐一判断会超时，这道题的解法是埃氏筛选法。
解题思路: 首先，将2到n范围内的所有整数写下来，其中最小的数字2是素数。将表中2的倍数都划去。表中剩余的最小数字是3，他不能被更小的数整除，所以是素数。再将表中所有3的倍数都划去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int countPrimes(int n) {
        bool is_prime[n];
        
        fill(is_prime, is_prime+n, true);
        
        is_prime[0] = is_prime[1]= false;
        int count = 0;
        for(int i = 2;i < n; i++){
            if(is_prime[i]){
                count++;
                for(int j = 2*i; j < n; j += i)
                    is_prime[j] = false;
                
            }
        }
        return count;
    }
};

自己整理的素数的有关内容
包括如何判断一个数是素数，以及判断一个区间内有多少个素数。
判断区间内素数的方法:(埃氏筛选法)
判断[a,b)间的素数的个数
构造一个数组[0, sqrt(b)],逐个筛选出这个区间的素数，将这个数的倍数扩展到[a,b)区间内，筛选出[a,b)区间内的素数